function swap(nums, i, j) {
  const temp = nums[i];
  nums[i] = nums[j];
  nums[j] = temp;
}

function bubbleSort(nums) {
  let results = nums.slice();
  for (let i = 0; i < results.length - 1; i++) {
    for (let j = 0; j < results.length - 1 - i; j++) {
      if (results[j] > results[j + 1]) swap(results, j, j + 1);
    }
  }
  return results;
}

function selectSort(nums) {
  let results = nums.slice();
  for (let i = 0; i < results.length - 1; i++) {
    let minIndex = i;
    for (let j = i; j < results.length; j++) {
      if (results[j] < results[minIndex]) minIndex = j;
    }
    swap(results, i, minIndex);
  }
  return results;
}

function insertSort(nums) {
  let results = nums.slice();
  for (let i = 1; i < results.length; i++) {
    for (let j = i; j >= 0 && results[j - 1] > results[j]; j--) {
      swap(results, j - 1, j);
    }
  }
  return results;
}

function quickSort1(nums) {
  if (nums.length <= 1) return nums.slice();
  const left = [];
  const right = [];
  const pivot = nums[0];
  for (let i = 1; i < nums.length; i++) {
    if (nums[i] < pivot) left.push(nums[i]);
    else right.push(nums[i]);
  }
  return [...quickSort1(left), pivot, ...quickSort1(right)];
}

function quickSort2(nums) {
  const results = nums.slice();
  subSort(results, 0, results.length - 1);
  return results;
}

function subSort(nums, start, end) {
  if (start > end) return;
  let i = start,
    j = end;
  while (i < j) {
    while (nums[i] < nums[j] && j > i) j--;
    swap(nums, i, j);
    while (nums[i] <= nums[j] && i < j) i++;
    swap(nums, i, j);
  }
  subSort(nums, start, i - 1);
  subSort(nums, i + 1, end);
}

function mergeSort(nums) {
  if (nums.length <= 1) return nums.slice();
  const mid = Math.floor(nums.length / 2);
  const nums1 = mergeSort(nums.slice(0, mid));
  const nums2 = mergeSort(nums.slice(mid));
  return merge(nums1, nums2);
}

function merge(nums1, nums2) {
  const results = [];
  let i = 0,
    j = 0;
  while (i < nums1.length && j < nums2.length) {
    if (nums1[i] < nums2[j]) results.push(nums1[i++]);
    else results.push(nums2[j++]);
  }
  while (i < nums1.length) results.push(nums1[i++]);
  while (j < nums2.length) results.push(nums2[j++]);
  return results;
}

function countingSort(nums) {
  const results = [];
  const max = Math.max(...nums);
  let buckets = new Array(max + 1).fill(0);
  nums.forEach((item) => {
    buckets[item]++;
  });
  buckets.forEach((n, i) => {
    while (n--) {
      results.push(i);
    }
  });
  return results;
}

function bucketSort(nums) {
  const results = [];
  const min = Math.min(...nums);
  const max = Math.max(...nums);
  const bucketNum = Math.floor((max - min) / 5) + 1;
  const buckets = new Array(bucketNum).fill(0).map(() => []);
  nums.forEach((item) => {
    const index = Math.floor((item - min) / 5);
    buckets[index].push(item);
  });
  buckets.forEach((bucket) => {
    bucket.sort();
    results.push(...bucket);
  });
  return results;
}

function radixSort(nums) {
  const temp = nums.slice();
  const buckets = new Array(10).fill(0).map(() => []);
  let base = 1;
  const max = Math.max(...temp);
  while (max >= base) {
    temp.forEach((item) => {
      const index = Math.floor(item / base) % 10;
      buckets[index].push(item);
    });
    temp.length = 0;
    buckets.forEach((bucket) => {
      temp.push(...bucket);
      bucket.length = 0;
    });
    base *= 10;
  }
  return temp;
}

console.log("bubbleSort", bubbleSort([1, 4, 2, 7, 5, 1, 0, 9, 4]));
console.log("selectSort", selectSort([1, 4, 2, 7, 5, 1, 0, 9, 4]));
console.log("insertSort", insertSort([1, 4, 2, 7, 5, 1, 0, 9, 4]));
console.log("quickSort1", quickSort1([1, 4, 2, 7, 5, 1, 0, 9, 4]));
console.log("quickSort2", quickSort1([1, 4, 2, 7, 5, 1, 0, 9, 4]));
console.log("mergeSort", mergeSort([1, 4, 2, 7, 5, 1, 0, 9, 4]));
console.log("countingSort", countingSort([1, 4, 2, 7, 5, 1, 0, 9, 4]));
console.log("bucketSort", bucketSort([1, 4, 2, 7, 5, 1, 0, 9, 4]));
console.log("radixSort", radixSort([10, 44, 22, 72, 5989, 100, 30, 99, 498]));
